package dynamicProgramming;

import java.util.Arrays;

/**
 *
 */
public class S1262可被三整除的最大和 {
    /**
     * 还是通过状态转移做动态规划, 3个状态。
     */

    /**
     * 66, 先排序, 然后判断一下总和的类型, 然后根据类型踢掉几个值就行。因为是3的倍数, 所以比较好办
     * 如果是5或者7的倍数, 这个办法就写不好了。
     */
    public int maxSumDivThree(int[] nums) {
        Arrays.sort(nums);
        int totalSum = 0;
        for(int i: nums){
            totalSum += i;
        }
        int flag = totalSum % 3;

        if(flag == 0){
            return totalSum;
        }else if(flag == 1){
            // 1个1或2个2
            int oneNum = Integer.MAX_VALUE;
            int oneNumCount = 0;
            for(int i: nums){
                if(i % 3 == 1){
                    oneNum = i;
                    oneNumCount = 1;
                    break;
                }
            }
            int[] twoNum = new int[]{Integer.MAX_VALUE, Integer.MAX_VALUE};
            int towNumCount = 0;
            for(int i: nums){
                if(i % 3 == 2){
                    twoNum[towNumCount] = i;
                    towNumCount++;
                    if(towNumCount == 2) break;
                }
            }
            if(oneNumCount == 0){
                if(towNumCount != 2){
                    return 0;
                }else{
                    return totalSum - twoNum[0] - twoNum[1];
                }
            }else{
                if(towNumCount != 2){
                    return totalSum - oneNum;
                }else{
                    return Math.max(totalSum - oneNum, totalSum - twoNum[0] - twoNum[1]);
                }
            }
        }else if(flag == 2){
            // 2个1或1个2
            int oneNum = Integer.MAX_VALUE;
            int oneNumCount = 0;
            for(int i: nums){
                if(i % 3 == 2){
                    oneNum = i;
                    oneNumCount = 1;
                    break;
                }
            }
            int[] twoNum = new int[]{Integer.MAX_VALUE, Integer.MAX_VALUE};
            int towNumCount = 0;
            for(int i: nums){
                if(i % 3 == 1){
                    twoNum[towNumCount] = i;
                    towNumCount++;
                    if(towNumCount == 2) break;
                }
            }
            if(oneNumCount == 0){
                if(towNumCount != 2){
                    return 0;
                }else{
                    return totalSum - twoNum[0] - twoNum[1];
                }
            }else{
                if(towNumCount != 2){
                    return totalSum - oneNum;
                }else{
                    return Math.max(totalSum - oneNum, totalSum - twoNum[0] - twoNum[1]);
                }
            }
        }
        return 0;
    }
}
